package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

/**
 * 面试题 04.10. 检查子树
 *
 * @Author liw
 * @Date 2021/5/13 14:26
 * @Version 1.0
 */
public class CheckSubTree {

    public boolean checkSubTree(TreeNode A, TreeNode B) {
        if (B == null) {
            return true;
        }
        if (A == null) {
            return false;
        }
        return find(A, B) ;
    }

    public boolean find(TreeNode A, TreeNode B) {
        if (A == null) {
            return false;
        }
        return check(A, B) || find(A.left, B) || find(A.right, B);
    }

    private boolean check(TreeNode A, TreeNode B) {
        if (B == null && A == null) {
            return true;
        }
        if (B == null || A == null) {
            return false;
        }
        return A.val == B.val && check(A.left, B.left) && check(A.right, B.right);
    }

}
